Метод дихотомии

Журнал Потенциал

Введение

Ваш друг задумал целое число от одного до десяти включительно. Он честно отвечает на ваши вопросы «да» или «нет». Какое минимальное число вопросов вам потребуется, чтобы гарантированно отгадать задуманное число?

Под фразой «гарантированно отгадать» следует понимать, что какое бы число из диапазона $[1..10]$ ни было загадано, задавая вопросы в соответствии с некоторым правилом, вам заведомо хватит $M$ вопросов, где $M$ — искомый минимум. Строго говоря, предлагается не только ответить на вопрос задачи, но и составить алгоритм отгадывания задуманного числа за минимальное число вопросов.

Биты и количество информации

Отвлечёмся и вспомним более простую задачу. Вы, конечно, помните, что такое один бит информации? Бит — это количество информации, уменьшающее степень неопределённости в два раза.

Классический пример — представим себе, что Вася не готовился к контрольной работе по математике, и может получить любую из оценок от двойки до пятерки. И вот, запыхавшийся Вася на пороге, и на вопрос «Как контрольная?» следует ответ: «Четыре!» Сколько бит информации сообщил вам Вася?

Для того, чтобы ответить на этот вопрос, разобьём наш вопрос «Как контрольная?» на этапы, причём таким образом, чтобы на каждом этапе неопределённость уменьшалась ровно в два раза. С точки зрения нормального человека это довольно необычный способ узнать ответ на вопрос. Но, тем не менее, приступим.

Первым этапом может быть, например, вопрос: «Оценка выше тройки?» Всего различных оценок четыре, этот вопрос разделяет их на две группы — «больше трёх» и «меньше либо равно трём». Очень важно, что эти группы одинаковы по количеству элементов — в каждой ровно по две возможных оценки. В первой группе находятся «отлично» и «хорошо», во второй — «удовлетворительно» и «плохо». Теперь нам предстоит определить одну оставшуюся оценку из двух, то есть уменьшить неопределённость ещё в два раза и получить ещё один бит информации. Отсюда следует, что искомое число бит в ответе Васи «Четвёрка!» равно двум — первый бит из четырёх возможных вариантов выбирает два, второй — выбирает из двух один.

Необходимо отметить, что разбиение потенциальных оценок на «группы» — исключительно дело вкуса, нужно лишь чтобы эти группы состояли из одинакового числа элементов. Вопрос первого этапа мог бы звучать, например, так: «Твоя оценка — двойка или пятерка?»

Пополам не делится

Искушённый читатель, должно быть, уже заметил, что в данном случае в ответ закрадываются степени двойки. И он не ошибся. Для того, чтобы передать один из двух возможных вариантов, требуется один бит. Два бита могут передать один из $2\cdot 2=4$ вариантов. Три бита — один из $2\cdot 2\cdot 2=8$ вариантов. С помощью $n$ бит можно передать один из $2^{n}$ вариантов.

Мы не будем подробно останавливаться на философском вопросе «А как же быть, если число вариантов не является степенью двойки?» Дотошного читателя не устраивает метод полутора землекопов.

Отгадаем число от 1 до 10

В какую минимальную степень $n$ необходимо возвести двойку, чтобы она стала больше десяти? В четвёртую, $2^{4}=16$. Из предыдущего абзаца следует, что четырёх вопросов будет достаточно для отгадывания. Первая часть задачи решена.

А как следует задавать вопросы, чтобы уложиться в дозволенные четыре вопроса? Уж точно не отгадывать число по порядку, начиная с единицы — это ведёт в худшем случае к девяти вопросам. Общее правило одно — нужно каждым вопросом уменьшать неопределённость в два раза. Если число вариантов не является степенью двойки, то в некоторых вопросах количество вариантов в «половинах» может различаться, но не более, чем на единицу. Итак, перед первым вопросом мы имеем десять различных вариантов. Десять пополам — пять. Спросим: «Задуманное число больше пяти?» Теперь самое главное не ошибиться нигде на единицу, не сказать не подумав «больше» вместо «больше либо равно» и наоборот.

После ответа на первый вопрос вариантов осталось пять. Нам нужно разбить их на группы, состоящие из двух и трёх элементов. Например, если выяснилось, что задуманное число больше пяти, корректно будет спросить: «Верно ли, что задуманное число больше либо равно восьми?»

Третьим вопросом мы снижаем число вариантов с двух до одного либо с трёх до двух. Если после второго вопроса осталось всего два варианта (например, на вопрос: «Число больше либо равно восьми?» последовал отрицательный ответ), то потребуется всего три, а не четыре вопроса. В любом случае, последним вопросом мы выбираем между двумя оставшимися числами и узнаём ответ.

Описанный метод называется методом деления пополам или, по-научному, дихотомией.

Упражнения

1

Сколько потребуется вопросов для того, чтобы отгадать:

• Число от одного до ста?
• В чью пользу и с каким счётом окончился матч в шахматы, который вёлся до трех побед и завершился победой одной из сторон?
• Определённую перестановку из четырёх различных элементов, например, порядок [карандаш, фломастер, ластик, калькулятор] из всех возможных способов выкладывания этих четырёх предметов в ряд.
• Какие вопросы следует задавать в предыдущем задании? Пусть для простоты элементы (предметы) называются $A$, $B$, $C$ и $D$.

2

Петя… нет, пусть будет, скажем, Андрей. Андрей предложил другой способ задавать вопросы. Первый вопрос: «Является ли твое число чётным?» Второй вопрос (если он нужен): «Является ли частное от деления твоего числа на два чётным?» В третьем вопросе изучается чётность частного от деления числа на четыре, в четвертом — на восемь, и вообще, в $n$-м вопросе изучается чётность частного от деления задуманного числа на $2^{n-1}$ (не забывайте, что $2^{0}=1$). Допустим, на пять вопросов Андрей получил ответы «Да, да, нет, да, нет» именно в таком порядке, и положим, что задуманное число лежит в диапазоне от $1$ до $32$. Какое число было задумано? Придумайте общий способ называть задуманное число по набору ответов «Да»/«Нет» при условии задавания вопросов по данному принципу.

3

Докажите, что «варьирование» числа вопросов, которое мы наблюдали в примере с «не всегда обязательным» четвёртым вопросом, возможно тогда и только тогда, когда число возможных вариантов не является степенью двойки.

Поиск элемента в массиве

Пусть мы имеем упорядоченный по неубыванию массив $M$ из, скажем, $10^{6}$ элементов. Нам необходимо найти индекс $i$ элемента, значение которого равно $x$:

$M[i]=x,\quad i=?$

Как решить эту задачу максимально быстро, то есть за возможно меньшее число обращений к массиву?

Ясно, что проверять все элементы массива начиная с первого — не самая лучшая идея. Необходимо придумать способ, который подстраивал бы следующую «попытку» на основании предыдущих. Не подойдет ли здесь метод дихотомии?

Вспомните, как вы ищете в словаре незнакомое слово — для простоты положим, что вы точно знаете написание. Разве вы пойдёте от начала словаря по всем словам? Если это словарь русского языка, в котором $40000=4\cdot 10^{4}$ слов, и ваша «скорость сканирования» составляет одно слово в секунду (не считая переворачивания страниц и перерывов на кофе), то процесс пролистывания словаря займёт у вас $40000/(60\cdot 60)\approx 11$ часов. Удивительно, что словари пользуются такой популярностью.

Вероятнее всего, вначале вы найдёте первую букву вашего слова (если вы, конечно, не герой Джона Траволты в фильме «Phenomenon», но в данной статье мы изучаем классические методы). Это обычно несложно сделать, учитывая то, что первые буквы в словаре обычно помечены специальным образом. Затем, когда мы знаем, с какой по какую страницу искать искомое слово, логично искать вторую букву (строго говоря, человеческий мозг использует несколько другой механизм поиска, который грубо можно аппроксимировать градиентным методом оптимизации, тем не менее, пример со словарем достаточно показателен), за ней третью и так далее. В итоге либо искомое слово будет найдено, либо найдутся два слова, между которыми оно должно быть, но его там нет.

Похожим образом мы ищем элемент в упорядоченном массиве. Пусть для простоты мы заранее проверили, что $M[1]<x$ и $M[N]>x$. Обратим внимание на $M\left[\left\lfloor {\frac {1+N}{2}}\right\rfloor \right]$. Если мы «промахнулись» мимо искомого элемента (что более чем вероятно для первой итерации) — не беда, мы теперь точно знаем в какой половине массива искать. Метод дихотомии преуспевает в решении и этой задачи.

Маленькая хитрость — при поиске элемента в массиве, и вообще, если подбираемый параметр — целое число, область поиска можно запоминать не как отрезок $[a;\,b]$ или интервал $(a;\,b)$, а как полуинтервал $[a;\,b)$. В большинстве случаев это упрощает переход от итерации к следующей, и сильно экономит время, затраченное впоследствии на отладку программы.

Немного математики

Если говорить на языке чистой математики, метод дихотомии позволяет найти ноль монотонной функции $f(x)$ на отрезке $[a;\,b]$, если на концах этого отрезка значения функции имеют различные знаки.

При этом если требуется точность $\varepsilon$, то есть если ответ должен отличаться от верного не более чем на $\varepsilon$, то число вычислений функции будет равно $\left\lceil \log _{2}{\frac {b-a}{2\cdot \varepsilon }}\right\rceil +1$. В случае подбора целого числа $\varepsilon$ равно ${\frac {1}{2}}$ (проверьте).

Данная формула справедлива для оптимальной реализации алгоритма. Обычно, программисты пишут так, что на каждом шаге значение функции на одном из концов отрезка вычисляется повторно (одно из значений программа «знала» на предыдущем шаге). И в примере программы, который мы привели ниже, количество вызовов функции (вычислений значения функции) в два раза больше оптимального. На такие «мелочи» промышленные программисты обычно не обращают внимания.

Если попытаться обобщить всё сказанное выше, то метод дихотомии снижает вычислительную сложность задачи поиска нужного значения функции $f$ с $N$ до $\log _{2}N$, если функция монотонна. Когда необходимо выполнить большое число операций поиска, имеет смысл вначале упорядочить данные (привести функцию к монотонной), а затем уже выполнять поиск методом дихотомии.

Отметим, что так называемая быстрая сортировка, в которой также присутствует идея деления пополам, имеет асимптотическую сложность $O(N\cdot \log N)$, и это лучшая возможная асимптотика времени сортировки .

Задача посложнее

В предыдущий раз мы отгадывали задуманное число. Число было целым, и его можно было отгадать либо не отгадать — точнее, всегда отгадать, вопрос стоял лишь о числе попыток. Решим задачу посложнее, а именно, научимся находить приближённые (численные) значения корней уравнений, используя метод деления пополам.

Рассмотрим уравнение, корень которого представляет собой трансцендентное число:

$e^{x}=x-2$

(следствие — в результате деления рационального отрезка пополам, как и в любом другом рациональном отношении, мы никогда не «попадем» случайно в трансцендентный корень). На отрезке $[0;\,2]$ данное уравнение имеет корень, наша задача — найти его с точностью до $10^{-10}$.

Начнём пошагово уточнять отрезок, на котором лежит корень, уменьшая его размер (область поиска) в два раза. Разделим данный нам отрезок пополам. В данном случае мы не связаны целыми числами, поэтому любой отрезок можно разделить ровно пополам.

Существует теорема, которая гласит, что если непрерывная функция $f(x)$ на двух концах отрезка $[a;\,b]$ имеет разные знаки, то она имеет корень (нулевое значение) на этом отрезке.

Обозначим концы исследуемого отрезка соответственно $a$ и $b$. Для нашей функции будет верно:

$f(a)<0$

$f(b)>0$

На первом шаге вычислим $c={\frac {b+a}{2}}$. Посмотрим на знак $f(c)$. Если $f(c)=0$ — редкая удача, мы нашли точное значение корня. В данном случае такая радужная перспектива нам не улыбается, потому как корень выражается трансцендентным числом.

Если мы не попали в корень, то, согласно принципу дихотомии, нам необходимо подготовить новый отрезок для поиска, в два раза короче, чем на данной итерации. Это просто: $f(c)$ либо положительна, либо отрицательна. Если $f(c)>0$, то возьмём для следующей итерации отрезок $[a;\,c]$, иначе — отрезок $[c;\,b]$.

На каждой итерации мы твёрдо знаем, что на отрезке $[a;\,b]$ есть искомый корень. Следовательно, число ${\frac {a+b}{2}}$ даёт значение корня с погрешностью, не превосходящей ${\frac {b-a}{2}}$. Таким образом, если наша цель — найти корень с погрешностью, не превосходящей $\varepsilon$, условие ${\frac {b-a}{2}}<\varepsilon$ является условием завершения итерационного процесса. Ответом будем считать середину последнего отрезка.

Пример программы на языке Си++

#include <iostream>
#include <cmath>
using namespace std;
const double epsilon = 1e-10;

double f(double x)
{
    return exp(x) - (x + 2);
};

void main()
{
    double a, b, c;
    a = 0;
    b = 2;
    while (b - a > epsilon)
    {
        c = (a + b) / 2;
        if(f(c) * f(b) >= 0)
            b = c;
        else
            a = c;
    };
    cout << (a + b) / 2 << endl;
}

Приведённая программа ищет ноль функции $f(x)=e^{x}-(x+2)$ на отрезке $[0;\,2]$ с точностью $10^{-10}$ методом дихотомии.

Сложная задача

Часто бывает непросто увидеть метод дихотомии в хорошей задаче по информатике. В завершение статьи приведём подобный пример — задача «Провода́» с полуфинала чемпионата мира по программированию ACM, проходившему в Санкт-Петербурге в октябре 2002 года.

На складе имеется $N$ проводов целочисленной длины. Необходимо из них получить $K$ кусков провода одинаковой и как можно большей длины $L$. Провода нельзя спаивать.

В первой строчке указаны числа $N$ и $K$, $1\leqslant N$, $K\leqslant 10^{4}$. Далее разделённые пробельными символами перечислены $N$ натуральных чисел — длины имеющихся проводов. Они не превосходят $10^{7}+1$.

Выведите целое максимальное число $L$ — такое, что можно из имеющихся проводов получить $K$ кусочков длины $L$.

Рассуждения о способах разрезания проводов, конечно, могут привести к решению, но гораздо более простой путь— дихотомия по длине про́вода. Функция общего числа проводов от проверяемой длины $L$ легко вычисляется, она, очевидно, является монотонной, и искать решение можно, например, на интервале от $L=1$ до $L=10^{7}+1$.

Задача сводится к классической дискретной дихотомии, и её решение оказывается на удивление простым.

Резюме

В руках опытного программиста метод дихотомии представляет собой мощный инструмент для поиска точных ответов в случае дискретных, и приближённых, но весьма точных, — в случае непрерывных задач.

В качестве самостоятельного упражнения предлагаем читателю сдать задачу 071 «Провода́» онлайновой системе проверки задач по программированию на сайте http://acm.mipt.ru.

См. также

• 9. Лекция: Однопараметрическая (одномерная) оптимизация. Методы одномерной оптимизации: метод дихотомии